﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using BI =System.Numerics.BigInteger;

namespace SRSTests
{
    public class RhoMethod
    {
        private static BI ZERO = BI.Zero;
        private static BI ONE = BI.One;
        private static BI TWO = new BI(2);

        private static List<BI> Divisors;
 
        private RhoMethod(){}
 
        /**
         * @param x x in (x*x + addition)%n expression
         * @param n n in (x*x + addition)%n expression, should be equal to factorized number
         * @param addition addition in (x*x + addition)%n expression
         * @return (x*x + addition)%n
         */
        private static BI GenerateRandomNumber(BI x, BI n, BI addition)
        {
            return (BI.Multiply(x, x) + (addition)) % n;
        }
 
        /**
         * @param number number to factorize
         * @param shift shift of Random Generator
         */
        private static void Factorization(BI number, BI shift)
        {
            if ((new BigInteger(number.ToByteArray())).isProbablePrime(10))//number.isProbablePrime(10) ) 
                Divisors.Add(number);
            else
            {
                BI x = TWO;
                BI y = TWO;
                BI divisor;
 
                if(  (BI)(number % (TWO)).CompareTo(ZERO) == 0 )    //test of divisibility by 2
                    divisor = TWO;
                else
                    divisor = ONE;
 
                while( divisor.CompareTo(ONE)==0 )
                {
                    x = GenerateRandomNumber(x, number, shift);
                    y = GenerateRandomNumber(y, number, shift);
                    y = GenerateRandomNumber(y, number, shift);
                    if ( x.CompareTo(y)==0 )
                    {
                        Divisors.Add(number);
                        return;
                    }
                    divisor = BI.GreatestCommonDivisor(BI.Abs(x-y),number);// x. .subtract(y).abs().gcd(number);
                }
                Factorization(divisor, shift);
                Factorization(BI.Divide(number,divisor), shift);
            }
        }
 
        /**
         * Returns Vector containing all prime factors of given number 
         * @param number number to factorize
         * @param certainty number of attemps of factorizating given number
         * @return Vector containing all prime factors of given number
         */
        public static List<BI> Factorize(BI number, int certainty)
        {
            Divisors = new List<BI>();
            Divisors.Add(number);
 
            for(int i=0; i<certainty; i++)
            {
                int length = Divisors.Count;
                while( (length--)>0 )
                {
                    number = Divisors.ElementAt(0);
                    Divisors.RemoveAt(0);
                    Factorization(number, new BI((i + 1)));
                }
            }
 
            return Divisors;
        }
 
        /**
         * Returns Vector containing all prime factors of given number
         * @param number number to factorize
         * @return Vector containing all prime factors of given number
         */
        public static List<BI> Factorize(BI number)
        {
            return Factorize(number, 1);
        }
    }
}
